Masala #0593

Xotira 65 MB Vaqt 1000 ms Qiyinchiligi 77 %
14

  

Plus-Minus

Plus va minus bir birini yoqtirmaydi. Ular joylashgan qishloqda \(N\) ta(\(1\) dan \(N\) gacha raqamlangan) chorraha va bu chorrahalarni bog'lab turuvchi \(M\) ta bir xil uzunlikdagi ikki tomonlama harakat qiladigan yo'llar mavjud. Plus minus turgan chorrahaga, minus esa plus turgan chorrahaga borishni istaydi ammo ikkisi bir chorrahada uchrashib qolishni istamaydi (umumiy yo'lda qarama qarshi harakatlanishi mumkin 1-testga qarang). Ikkisi ham optimal harakat qilib plus \(N-\)chorrahaga, minus \(1-\)chorrahaga borishi kerak. Ularning tezliklari bir xil va doim harakatda qachonki ikkisi ham manziliga bir vaqtda yetib kelsa harakatni to'xtatadi. Dastlab plus \(1-\)chorrahada, minus esa \(N-\)chorrahada joylashgan.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrda \(N(2\leq N\leq200)\) va \(M(1\leq M\leq N(N-1)/2)\) ikkita natural son mos ravishda chorrahalar va yo'llar soni. Keyingi \(M\) ta satrda \(u, v(1\leq u,v\leq N)\)  \((u\neq v)\) chorrahalar o'rtasida yo'l mavjudligi. 


Chiquvchi ma'lumotlar:

Chiqish faylining birinchi satrda plus va minus ikkisi ham bir xil vaqtda manziliga yetib olguncha minimal tashrif buyurgan chorrahalar soni \(K\) va keyingi 2 ta satrda mos ravishda "P:" va "M:" belgilari va K tadan son ketma-ket tashrif buyurish chorrahalarni probel bilan ajratilgan holda chop eting (agar bunday yechimlar bir nechta bo'lsa istalganini, dastlab plusni harakatini keyingi satrda minusni harakatini chop eting). Agar ikkisi bir vaqtda manzilga borishning imkoni bo'lmasa "Infinite!" so'zini ni chop eting.


Misollar
# input.txt output.txt
1
2 1
1 2
2
P: 1 2
M: 2 1
2
5 4
1 2
4 3
3 1
5 3
Infinite!
3
7 6
1 6
1 5
7 5
3 4
2 7
5 3
7
P: 1 5 3 4 3 5 7
M: 7 2 7 5 1 6 1
Izoh:

1-test: Plus va minus umumiy yo'lda qarama qarshi harakatda o'tib ketadi va ikkisixam bir vaqtda ma'nzilga yetib keladi.

2-test: Plus va minus hech qachon ma'nziliga yetib borishining imkoni bo'lmaydi.

3-test: Plus va minus ma'nziliga yetib borishi uchun harakati rasimda tasvirlangan(plus-yashil va minus-qizil rang bilan ifodalangan). 

sample-images

 

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin